REPORTE TRABAJO 1: SOLUCIÓN DE PROBLEMAS DE OPTIMIZACIÓN CON MÉTODOS HEURÍSTICOS
REDES NEURONALES Y ALGORITMOS BIOINSPIRADOS
Presentado por:
Leonardo Federico Corona Torres
David Escobar Ruiz
Johan Sebastian Robles Rincón
Sebastián Soto Arcila
Profesor: Juan David Ospina Arango
Monitor: Andrés Mauricio Zapata Rincón
Universidad Nacional de Colombia
Facultad de Minas
Ingeniería de
Sistemas e Informática
09 de julio de 2025
Contenidos
- Introducción
- Metodología
- 1. Optimización numérica
- 1.1. Selección e implementación de las funciones de prueba
- 1.1.1. Breve explicación de las funciones de prueba para problemas de optimización
- 1.1.2. Implementación de funciones de graficación
- 1.1.3. Función de Rosenbrock
- 1.1.4. Función de Rastrigin
- 1.2. Método de descenso de gradiente
- 1.2.1. Implementación en R de descenso por gradiente
- 1.2.2. Optimización de la función de Rosenbrock en 2 dimensiones
- 1.2.3. Optimización de la función de Rosenbrock en 3 dimensiones
- 1.2.4. Optimización de la función de Rastrigin en 2 dimensiones
- 1.2.5. Optimización de la función de Rastrigin en 3 dimensiones
- 1.2.6. Conclusiones método de desenso del gradiente
- 1.3. Método de evolución diferencial
- 1.3.1. Implementación en R de evolución diferencial
- 1.3.2. Optimización de la función de Rosenbrock en 2 dimensiones
- 1.3.3. Optimización de la función de Rosenbrock en 3 dimensiones
- 1.3.4. Optimización de la función de Rastrigin en 2 dimensiones
- 1.3.5. Optimización de la función de Rastrigin en 3 dimensiones
- 1.3.6. Conclusiones método de evolución diferencial
- 1.4. Método de optimización de partículas
- 1.4.1. Implementación en R de optimización de partículas
- 1.4.2. Optimización de la función de Rosenbrock en 2 dimensiones
- 1.4.3. Optimización de la función de Rosenbrock en 3 dimensiones
- 1.4.4. Optimización de la función de Rastrigin en 2 dimensiones
- 1.4.5. Optimización de la función de Rastrigin en 3 dimensiones
- 1.4.6. Conclusiones método de evolución diferencial
- 1.5. Método de algoritmos evolutivos
- 1.5.1. Implementación en R de algoritmos evolutivos
- 1.5.2. Optimización de la función de Rosenbrock en 2 dimensiones
- 1.5.3. Optimización de la función de Rosenbrock en 3 dimensiones
- 1.5.4. Optimización de la función de Rastrigin en 2 dimensiones
- 1.5.5. Optimización de la función de Rastrigin en 3 dimensiones
- 1.5.6. Cálculo de estadísticas y análisis
- 1.5.7. Conclusiones método de algoritmos evolutivos
- 2. Optimización combinatoria
- 2.1. Planteamiento del problema
- 2.2. Implementación Método de Colonia de hormigas
- 2.3. Implementación Método de Algoritmos Genéticos
- 2.5. Conclusiones
- Conclusión General
- Reporte de contribución individual
- Repositorio de GitHub del proyecto
- Bibliografía
Introducción
El presente trabajo trata algunos de los métodos más relevantes de optimización numérica basada en manipulaciones del gradiente de una función objetivo (función a optimizar) y también algoritmos heurísticos basados en el comportamiento de la naturaleza, como lo son los algoritmos evolutivos. Todos estos métodos pueden llegar a ser útiles en distintos contextos en los que se busca optimizar una función para algún fin, como encontrar la mejor ruta entre ciudades o optimizar una función de pérdida en un contexto de aprendizaje de máquina. Cada método tiene particularidades interesantes que se van a explorar de manera general por medio de una breve implementación y ejecución con dos funciones muy utilizadas para probar algoritmos de optimización: la función de Rosenbrock y la función de Rastrigin.
Metodología
Para implementar y documentar la optimización se emplea R Markdown, combinando código R y texto explicativo. Se utilizan librerías para renderizar gráficos y animaciones, librerías para implementar los métodos heurísticos y librerías para manipular los datos. Para los casos 3D (tres variables) es difícil visualizar directamente la función de 3 dimensiones (espacio de 4 variables), por lo que se mostrarán únicamente los puntos óptimos alcanzados.
Parte 1. Optimización numérica
1.1 Selección e implementación de las funciones de prueba
Para observar el comportamiento de cada uno de los métodos de optimización implementados, se optó por la selección de dos funciones de prueba estándar para evaluar algoritmos de optimización: Función de Rosenbrock y Función de Rastrigin. Debido a su complejidad, ambas funciones son indicadores útiles para comparar la eficacia de optimizadores como los AG.
Previo a la implementación de los algoritmos en el lenguaje R y previo a la recopilación de resultados y la derivación de conclusiones a partir de estos, el equipo decidió realizar una breve investigación general de lo que son las funciones de prueba para problemas de optimización. La investigación se realizó de tal forma que, una vez concluída, se pudieran comprender los conceptos hasta el punto de estar en las capacidades responder las siguientes preguntas implícitamente en una breve sección de este trabajo:
¿Qué es una función de prueba en optimización?
¿Para qué se utiliza una función de prueba en optimización?
¿Cómo se pueden clasificar las funciones de prueba?
¿Cuáles son algunas de las funciones de prueba más utilizadas?
A continuación se presenta dicha sección para luego continuar con el estudio más detallado de las funciones escogidas.
1.1.1 Breve explicación de las funciones de prueba para problemas de optimización
Según (Yang, 2010), una función de prueba es una función con unas propiedades especiales que permite probar si el rendimiento de un método de optimización implementado es aceptable bajo las condiciones especiales que impone la función de prueba.
Esto es especialmente útil para verificar que el método sea eficiente bajo distintas condiciones en las que se espera que se implemente, como por ejemplo, casos en los que la función tiene múltiples mínimos y/o máximos locales.
Según (Molga, 2005), las funciones de prueba se pueden ubicar en una de las siguientes clases, todas siendo funciones continuas:
- Clase 1: Unimodal, convexa, multidimensional.
- Clase 2: Multimodal, dos dimensiones con un número pequeño de extremos locales.
- Clase 3: Multimodal, dos dimensiones con un gran número de extremos locales.
- Clase 4: Multimodal, multidimensional, con un número amplio de extremos locales.
En el caso de las funciones elegidas, la función de Rosenbrock se clasificaría como Clase 3 y la de Rastrigin como Clase 2.
Como ejemplo, en la Figura 1 se presentan algunas funciones de prueba que no se eligieron para este trabajo, pero que son igual de relevantes, importantes y comúnmente utilizadas en la práctica (Molga, 2005):
Función de De Jong (Clase 1).
Función de Griewangk (Clase 2).
Función de Langermann (Clase 3).
Función de Ackley (Clase 4).
1.1.2 Función de Rosenbrock
Es una función no convexa introducida por Rosenbrock en 1960 (Wikipedia, s.f., Rosenbrock function). Su paisaje forma un valle curvo estrecho que dificulta la convergencia hacia el mínimo.
Definición en n dimensiones:
\(f(X) = \sum_{i=1}^{n-1}100(X_{i+1}-X_i^2)^2 + (1-X_i)^2\) (1)
Definición en 2D:
\(f(x,y)= 100(y-x^2)^2 + (1-x)^2\) (2)
Definición en 3D:
\(f(x,y,z)=100[(y-x^2)^2+(z-y^2)^2] + (1-x)^2 + (1-y)^2\) (3)
Algunas características y propiedades importantes son las siguientes:
El mínimo global está dado por los puntos que cumplen con \(x_1,...,x_n =1\)
El dominio de búsqueda consiste de todo el espacio real, es decir, donde cada punto cumple con \(-\infty \leq X_i \leq \infty, 1 \leq i \leq n\).
Conocida también como la función banana de Rosenbrock.
Tiene forma de valle, el cual es trivial encontrarlo. Sin embargo, la convergencia al mínimo global es difícil.
Estas son algunas hipótesis y expectativas que se tuvieron para el rendimiento de cada método implementado con esta función:
Método de descenso de gradiente:
- Si se ubica el punto inicial sobre las rectas tangentes con mayor gradiente a la función entonces el método llegará más rápido a un mínimo.
- Por el contrario, si la recta tangente tiene una gradiente más cercana a cero, el método llegará más lentamente, es decir, requerirá de más iteraciones para llegar al punto mínimo.
Método de algoritmos evolutivos:
- Los criterios para seleccionar los individuos a reproducir va a ser muy importante para el rendimiento del método.
Método de optimización de partículas:
- Este método no va a tener muchas dificultades para encontrar el punto óptimo es la función de Rosenbrock.
- El criterio para parar las iteraciones no va a cambiar mucho los resultados en este caso.
Método de evolución diferencial:
- Se comporta similar a los métodos evolutivos en 2 dimensiones.
La implementación de la función de Rosenbrock en 2, 3 y N dimensiones se muestra a continuación:
# 2 Dimensiones
f_rosenbrock_2d <- function(x, y) {
f_value <- 100*(y-(x^2))^2 + ((1-x)^2)
return(f_value)
}
# 3 Dimensiones
f_rosenbrock_3d <- function(x, y, z) {
f_value <- 100*((y-x^2)^2 + (z-y^2)^2) + (1-x)^2 + (1-y)^2
return(f_value)
}
# N Dimensiones
f_rosenbrock <- function(x){
x_1 <- tail(x, -1)
x <- head(x, -1)
z <- sum((100*((x_1-(x^2))^2))+((1-x)^2))
return(z)
}Las gráficas de la función de Rosenbrock en 2 y 3 dimensiones se muestran a continuación:
Gráfica de la función de Rosenbrock 2D
Gráfica de la función de Rosenbrock 3D
1.1.3 Función de Rastrigin
La función Rastrigin (1974) es una función no convexa y altamente multimodal, con numerosos mínimos locales, lo que la hace difícil de optimizar (Wikipedia, s.f., Rastrigin function).
Presenta múltiples mínimos locales dispuestos de forma regular, lo que lo convierte en un desafío típico para algoritmos de optimización.
Definición en n dimensiones:
\(f(X)=An + \sum_{i=1}^n[X_i^2 -A\cos(2\pi X_i)], A=10\) (4)
Definición en 2D:
\(f(x,y)=x^2+y^2+A[2-\cos(2\pi x) - \cos(2\pi y)], A=10\) (5)
Definición en 3D:
\(f(x,y)=x^2+y^2+z^2+A[3-\cos(2\pi x) - \cos(2\pi y)-\cos(2\pi z)], A=10\) (6)
Algunas características y propiedades importantes son las siguientes:
El mínimo global se alcanza cuando el vector es un vector nulo, es decir, \(X=[0,...,0]\) para n dimensiones.
El dominio de búsqueda cumple con \(-5.12 \leq X_i \leq 5.12\).
Particularmente, hallar el mínimo de esta función es un problema difícil debido a la larga cantidad de mínimos locales.
Estas son algunas hipótesis y expectativas que se tuvieron para el rendimiento de cada método implementado con esta función:
Método de descenso de gradiente:
- El éxito del método en alcanzar un mínimo dependerá enormemente del punto inicial elegido debido a los múltiples mínimos locales que tiene esta función.
Método de algoritmos evolutivos:
- Es importante hacer una buena representación de los individuos, ya que el rendimiento puede variar dependiendo de la selección.
- La población inicial debe ser representativa, diferentes entre ellos y que no sean demasiados. Para esta función en particular encontrar la solución óptima va a depender mucho de la probabilidad de mutación
Método de optimización de partículas:
- La ubicación de la nube de partículas va a afectar el rendimiento en esta función, ya que el algoritmo puede quedarse estancado en un mínimo local si la ubicación no es la mejor.
- El criterio para detener el algoritmo debe estar bien ajustado, para evitar estancamientos.
Método de evolución diferencial:
- Es más eficiente que los otros métodos evolutivos ya que su fuerte son las múltiples dimensiones.
La implementación de la función de Rastrigin en 2, 3 y N dimensiones se muestra a continuación:
# 2 Dimensiones
f_rastrigin_2d <- function(x, y) {
A = 10
f_value <- x^2 + y^2 + A*(2 - cos(2*pi*x) - cos(2*pi*y))
return(f_value)
}
# 3 Dimensiones
f_rastrigin_3d <- function(x, y, z) {
A = 10
f_value <- x^2 + y^2 + z^2 + A*(3 - cos(2*pi*x) - cos(2*pi*y) - cos(2*pi*z))
return(f_value)
}
# N Dimensiones
f_rastrigin <-function(x){
A <- 10
n <- length(x)
z <- (A*n) + sum(x^2 - A*cos(2*pi*x))
return(z)
}Las gráficas de la función de Rastrigin en 2 y 3 dimensiones se muestran a continuación:
Gráfica de la función de Rastrigin 2D
Gráficas de la función de Rastrigin 3D
1.2 Método de descenso de gradiente
El método de optimización por descenso de gradiente es una técnica iterativa utilizada para encontrar el mínimo de una función. Consiste en actualizar sucesivamente los valores de las variables en la dirección opuesta al gradiente de la función, con el objetivo de reducir su valor en cada paso.
En nuestro caso, se utilizaron las siguientes variables para implementar el método: X₀, que representa la condición inicial del algoritmo; H, que define el tamaño de la ventana para el cálculo de la derivada numérica; y ETA, que corresponde a la tasa de aprendizaje, es decir, el tamaño del paso que se da en cada iteración hacia el mínimo.
1.2.1 Implementación en R de descenso de gradiente
# Implementación completa de optimizador multivariado por descenso de gradiente
optimizador_mult_numdev <- function(x0,fun,max_eval=100,h=0.01,eta=0.01){
x <- matrix(NA,ncol =length(x0), nrow = max_eval)
x[1,] <- x0
for (i in 2:max_eval){
num_grad_fun <- num_grad(x[i-1,],fun,h)
H <- matriz_hessiana(x[i-1,],fun,h)
cambio <- - eta*solve(H)%*%num_grad_fun
x[i,] <- x[i-1,] + cambio
cambio_opt <- sqrt(sum((x[i-1,]-x[i,])^2))
if (cambio_opt<0.00001){
break
}
}
return(x[1:i,])
}1.2.2 Optimización de la función de Rosenbrock en 2 dimensiones
sol_rosen2d <- optimizador_mult_numdev(f_rosenbrock, x0=c(-4,-4), h=0.005, eta=0.5)La siguiente animación muestra el desempeño de la optimización a traves de su trayectoria:
Animación de la optimización de Rosenbrock 2D
1.2.3 Optimización de la función de Rosenbrock en 3 dimensiones
sol_rosen3d <- optimizador_mult_numdev(f_rosenbrock, x0=c(-4,-4,-4), h=0.005, eta=0.5)En la siguiente tabla de muestran el comportamiento cada 10 iteraciones:
show_table("./Parte 1/Descenso de gradiente/rosenbrock_iter_grad.csv")Iteracion <int> |
X1 <dbl> |
X2 <dbl> |
X3 <dbl> |
f_x <dbl> |
|
|---|---|---|---|---|---|
| 10 | 10 | -0.4746588 | -0.958089003 | 0.551655990 | 1.594659e+02 |
| 20 | 20 | 0.1573142 | 0.008101639 | -0.002158858 | 1.722186e+00 |
| 30 | 30 | 0.8622383 | 0.739978128 | 0.539436307 | 9.441027e-02 |
| 40 | 40 | 0.9951835 | 0.990348334 | 0.980616739 | 1.195241e-04 |
| 50 | 50 | 0.9970042 | 0.994027256 | 0.988090002 | 4.465851e-05 |
Tabla 1. Tabla de ejecución de optimización de Rosenbrock 3D utilizando Descenso de Gradiente
1.2.4 Optimización de la función de Rastrigin en 2 dimensiones
sol_ras2d <- optimizador_mult_numdev(f_rastrigin, x0=c(4.5,4.5), h=0.005, eta=2)La siguiente animación muestra el desempeño de la optimización a traves de su trayectoria:
Animación de la optimización de Rastrigin 2D
1.2.5 Optimización de la función de Rastrigin en 3 dimensiones
sol_ras3d <- optimizador_mult_numdev(f_rastrigin, x0=c(-4,-4,-4), h=0.005, eta=2)En la siguiente tabla de muestran el comportamiento cada 10 iteraciones:
show_table("./Parte 1/Descenso de gradiente/rastrigin_iter_grad.csv")Iteracion <int> |
X1 <dbl> |
X2 <dbl> |
X3 <dbl> |
f_x <dbl> |
|
|---|---|---|---|---|---|
| 10 | 10 | -3.957646 | -3.957646 | -3.957646 | 48.04492 |
| 20 | 20 | -3.954028 | -3.954028 | -3.954028 | 48.14587 |
| 30 | 30 | -3.947836 | -3.947836 | -3.947836 | 48.35321 |
| 40 | 40 | -3.933194 | -3.933194 | -3.933194 | 49.01439 |
| 50 | 50 | -3.399662 | -3.399662 | -3.399662 | 88.90609 |
| 60 | 60 | -4.984220 | -4.984220 | -4.984971 | 74.67761 |
| 70 | 70 | -4.984487 | -4.984487 | -4.985301 | 74.68100 |
| 80 | 80 | -4.984775 | -4.984775 | -4.985663 | 74.68479 |
| 90 | 90 | -4.985087 | -4.985087 | -4.986062 | 74.68906 |
| 100 | 100 | -4.985429 | -4.985429 | -4.986505 | 74.69392 |
Tabla 2. Tabla de ejecución de optimización de Rastrigin 3D utilizando Descenso de Gradiente
1.2.6 Conclusiones método de desenso del gradiente
El método de optimización por descenso de gradiente se caracteriza por su simplicidad y facilidad de implementación, lo que lo convierte en una herramienta útil para funciones con superficies suaves y relativamente simples. Sin embargo, al aplicarse a funciones altamente no convexas como la función de Rastrigin, este método presenta limitaciones significativas, ya que tiende a quedar atrapado en mínimos locales, dificultando la convergencia hacia una solución global óptima.
1.3 Método de evolución diferencial
La evolución diferencial es un algoritmo de optimización inspirado en la evolución biológica. Funciona manteniendo una población de soluciones, y mejorándolas generación tras generación mediante operaciones de mutación, recombinación y selección.
- Mutación: se combinan 3 individuos distintos de la población para crear una variante.
- Recombinación: se mezcla esa variante con el individuo actual.
- Selección: se escoge el mejor entre el original y el nuevo.
Este proceso se repite varias veces hasta encontrar una solución óptima.
Las variables son: dim, que representa la cantidad de dimensiones o variables del problema; NP, que indica el tamaño de la población o número de soluciones en cada generación; F, que es el factor de mutación y determina la intensidad de la perturbación aplicada a las soluciones; CR, que corresponde a la tasa de recombinación y controla la probabilidad de intercambio de componentes entre vectores; gens, que define el número total de generaciones o iteraciones del algoritmo; y bounds, que establece los límites inferior y superior del espacio de búsqueda para cada dimensión.
1.3.1 Implementación en R de evolución diferencial
evolucion_diferencial <- function(fun_obj, dim = 2, NP = 30, F = 0.8, CR = 0.9,
gens = 100, bounds = c(-5, 5)) {
# Inicializar población
poblacion <- matrix(runif(NP * dim, bounds[1], bounds[2]), ncol = dim)
fitness <- apply(poblacion, 1, fun_obj)
historial <- numeric(gens)
mejores <- matrix(NA, gens, dim)
for (gen in 1:gens) {
for (i in 1:NP) {
# Seleccionar 3 índices distintos
indices <- sample(setdiff(1:NP, i), 3)
x1 <- poblacion[indices[1], ]
x2 <- poblacion[indices[2], ]
x3 <- poblacion[indices[3], ]
# Mutación
mutado <- x1 + F * (x2 - x3)
# Recombinar
trial <- poblacion[i, ]
jrand <- sample(1:dim, 1)
for (j in 1:dim) {
if (runif(1) < CR || j == jrand) {
trial[j] <- mutado[j]
}
}
# Selección
if (fun_obj(trial) < fitness[i]) {
poblacion[i, ] <- trial
fitness[i] <- fun_obj(trial)
}
}
# Guardar mejor resultado
best_idx <- which.min(fitness)
historial[gen] <- fitness[best_idx]
mejores[gen, ] <- poblacion[best_idx, ]
}
list(mejor = poblacion[which.min(fitness), ],
valor = min(fitness),
historial = historial,
trayectoria = mejores)
}1.3.2 Optimización de la función de Rosenbrock en 2 dimensiones
En este gráfico se muestran las curvas de nivel de la función de Rosenbrock en dos dimensiones. Estas curvas representan líneas donde la función tiene igual valor, y el valle curvado al centro es donde está el mínimo global (en el punto (1,1)(1,1)).
La línea roja representa la trayectoria que siguió el algoritmo de evolución diferencial durante las iteraciones. Se puede observar cómo el enjambre de soluciones se fue acercando progresivamente hacia el mínimo, mejorando su posición en cada generación.
Animación de la optimización de Rosenbrock 2D
El resultado final obtenido fue: [1] 1.000000 1.000001 Valor mínimo encontrado: 1.91e-12
1.3.3 Optimización de la función de Rosenbrock en 3 dimensiones
En esta parte del informe se muestran los resultados numéricos para la optimización de las funciones en 3D. Dado que no se puede visualizar fácilmente en una gráfica 3D de trayectoria, se reportan las mejores posiciones y valores obtenido.
show_table("./Parte 1/Evolucion_Diferencial/rosenbrock_iter_evd.csv")Iteracion <int> |
X1 <dbl> |
X2 <dbl> |
X3 <dbl> |
f_x <dbl> |
|
|---|---|---|---|---|---|
| 10 | 10 | -0.5851768 | 0.1130689 | 0.8649437 | 8.117769e+01 |
| 20 | 20 | 0.8804582 | 0.5209831 | 0.4780407 | 1.097578e+01 |
| 30 | 30 | 0.6909606 | 0.4626611 | 0.3574320 | 2.461728e+00 |
| 40 | 40 | 0.8538862 | 0.6791208 | 0.3539351 | 1.525006e+00 |
| 50 | 50 | 0.6618927 | 0.4963945 | 0.2269164 | 7.457276e-01 |
| 60 | 60 | 0.8752932 | 0.7583245 | 0.5976751 | 1.312261e-01 |
| 70 | 70 | 0.9673312 | 0.9327385 | 0.8779734 | 1.284198e-02 |
| 80 | 80 | 1.0023756 | 1.0066111 | 1.0136724 | 4.096946e-04 |
| 90 | 90 | 1.0023756 | 1.0066111 | 1.0136724 | 4.096946e-04 |
| 100 | 100 | 0.9998260 | 0.9998014 | 0.9996265 | 2.357928e-06 |
Tabla 3. Tabla de ejecución de optimización de Rosenbrock 3D utilizando Evolución Diferencial
1.3.4 Optimización de la función de Rastrigin en 2 dimensiones
Aquí se grafican las curvas de nivel de la función de Rastrigin, que es multimodal, es decir, tiene muchos mínimos locales (patrón ondulado). La búsqueda es mucho más compleja que en Rosenbrock.
La línea azul muestra cómo la evolución diferencial se mueve por el espacio de búsqueda y logra escapar de los mínimos locales hasta acercarse al óptimo global, que se encuentra en (0,0)(0,0).
Animación de la optimización de Rastrigin 2D
Resultado obtenido: [1] 2.176697e-06 -2.015785e-07 Valor mínimo: 9.48e-10
1.3.5 Optimización de la función de Rastrigin en 3 dimensiones
En este caso, el algoritmo encontró una solución cercana al mínimo global, aunque no exacta. Esto es esperable, ya que Rastrigin es mucho más difícil en 3D debido a la gran cantidad de mínimos locales.
show_table("./Parte 1/Evolucion_Diferencial/rastrigin_iter_evd.csv")Iteracion <int> |
X1 <dbl> |
X2 <dbl> |
X3 <dbl> |
f_x <dbl> |
|
|---|---|---|---|---|---|
| 10 | 10 | 1.064334561 | 1.037971464 | -0.086056745 | 4.73335450 |
| 20 | 20 | 1.057313204 | 1.012050066 | 0.021733277 | 2.90578529 |
| 30 | 30 | 1.057313204 | 1.012050066 | 0.021733277 | 2.90578529 |
| 40 | 40 | 0.036246808 | 1.031428503 | 1.009576812 | 2.55506463 |
| 50 | 50 | -1.004720490 | -0.025677269 | 0.022997883 | 1.24913224 |
| 60 | 60 | 0.988499542 | -0.008651518 | 0.010258072 | 1.03894216 |
| 70 | 70 | 0.988499542 | -0.008651518 | 0.010258072 | 1.03894216 |
| 80 | 80 | -0.025075277 | 0.041071447 | 0.020016885 | 0.53668971 |
| 90 | 90 | 0.010524114 | 0.009941041 | 0.006215324 | 0.04922793 |
| 100 | 100 | -0.004061259 | -0.007504267 | 0.001244800 | 0.01474968 |
Tabla 4. Tabla de ejecución de optimización de Rastrigin 3D utilizando Evolución Diferencial
1.3.6 Conclusiones método de evolución diferencial
El algoritmo logró encontrar soluciones muy cercanas al mínimo global en las funciones de Rosenbrock y Rastrigin, tanto en 2D como en 3D.
En la función de Rosenbrock, se observó una convergencia estable y precisa, especialmente en dos dimensiones.
En la función de Rastrigin, que presenta muchos mínimos locales, el método evitó caer en estos y alcanzó buenos resultados.
El rendimiento se mantuvo sólido en tres dimensiones, aunque con una ligera pérdida de precisión en Rastrigin 3D debido a su complejidad.
Fue más robusto que el descenso por gradiente en funciones multimodales, ya que no necesita derivadas ni depende del punto inicial.
La evolución diferencial demostró ser un método confiable y efectivo para resolver problemas de optimización continua.
1.4 Método de optimización de partículas
El método de optimización por enjambre de partículas (PSO, por sus siglas en inglés) es un algoritmo inspirado en el comportamiento colectivo de animales como bandadas de aves o bancos de peces. Funciona mediante un conjunto de partículas (soluciones potenciales) que exploran el espacio de búsqueda moviéndose en función de su propia experiencia y la de sus vecinas. Cada partícula ajusta su posición y velocidad iterativamente para acercarse a la mejor solución conocida, guiada por su mejor posición histórica y la mejor posición global encontrada por el enjambre. Con el tiempo, las partículas tienden a converger hacia una solución óptima o cercana al óptimo.
1.4.1 Implementación en R de optimización de partículas
Se utiliza el paquete pos para implementar el método de la optimización de partículas. Adicionalmente, se implementa una función adicional para crear las animaciones del método de optimización.
1.4.2 Optimización de la función de Rosenbrock en 2 dimensiones
Animación de la optimización de Rosenbrock 2D con PSO
1.4.3 Optimización de la función de Rosenbrock en 3 dimensiones
show_table("./Parte 1/Enjambre de partículas/rosenbrock_iter_pso.csv")iteracion <int> |
mejor_valor_enjambre <dbl> |
mejor_posicion_enjambre <chr> |
diferencia_abs <dbl> |
|
|---|---|---|---|---|
| 10 | 10 | 331.7666 | -9.51355277365643, 9.55627294905859, 9.52381833492284 | 1.466955e-01 |
| 20 | 20 | 331.7941 | -9.54545504914603, 9.58341360681124, 9.52306164187284 | 2.136272e-01 |
| 30 | 30 | 332.0698 | -9.53590113241727, 9.54041577588653, 9.56011765629112 | 4.444692e-01 |
| 40 | 40 | 331.7437 | -9.52423268435948, 9.52725725394154, 9.5811887290536 | 3.001570e-01 |
| 50 | 50 | 331.8203 | -9.5142541282931, 9.52908789764021, 9.54155305396948 | 1.560163e-01 |
| 60 | 60 | 332.0383 | -9.57209212541967, 9.54481467451097, 9.54675150787573 | 8.420885e-02 |
| 70 | 70 | 332.1110 | -9.54430273204136, 9.53782738376895, 9.54921607427319 | 1.458293e-02 |
| 80 | 80 | 332.1347 | -9.54429172045766, 9.54774735662854, 9.54976723459583 | 1.992581e-04 |
| 90 | 90 | 332.1375 | -9.54743114478767, 9.55201686251299, 9.54880483650736 | 3.227996e-03 |
| 100 | 100 | 332.1393 | -9.55020210478277, 9.54848826976327, 9.54919167244683 | 2.639027e |
Tabla 5. Tabla de ejecución de optimización de Rosenbrock 3D utilizando Optimización de Partículas
1.4.4 Optimización de la función de Rastrigin en 2 dimensiones
Animación de la optimización de Rastrigin 2D con PSO
1.4.5 Optimización de la función de Rastrigin en 3 dimensiones
# Parámetros a utilizar
n <- 3
lower_bounds <- -5
upped_bounds <- 5
# Ejecución del método
o_pso <- particle_swarm_optimization(n,f_rastrigin,lower_bounds,upper_bounds)show_table("./Parte 1/Enjambre de partículas/rastrigin_iter_pso.csv")iteracion <int> |
mejor_valor_enjambre <dbl> |
mejor_posicion_enjambre <chr> |
diferencia_abs <dbl> |
|---|---|---|---|
| 10 | 332.1333 | 9.55062500864904, 9.54736155842502, 9.55448763975004 | 1.325873e+00 |
| 20 | 331.5406 | 9.52357446958727, 9.56685821317542, 9.50250205784094 | 4.792065e-01 |
| 30 | 331.5791 | 9.56526091259586, 9.600114687037, 9.56518504530152 | 2.707836e-01 |
| 40 | 331.9865 | 9.57682593047023, 9.5526306447749, 9.54163679429817 | 1.399468e-01 |
| 50 | 331.9818 | 9.5228388940773, 9.54025472242996, 9.5413775386611 | 3.082020e-01 |
| 60 | 332.0952 | 9.56461187832995, 9.54815999520477, 9.54883681982856 | 1.753033e-02 |
| 70 | 332.1266 | 9.55580067863994, 9.552365632497, 9.54528606283767 | 5.561529e-03 |
| 80 | 332.1387 | 9.54750362349369, 9.5488424083441, 9.55047112210335 | 3.497472e-04 |
| 90 | 332.1391 | 9.54792760233839, 9.54882584945718, 9.54820282423739 | 1.332779e-04 |
| 100 | 332.1393 | 9.54833176359814, 9.54891927922634, 9.54828740925572 | 1.924380e-05 |
Tabla 6. Tabla de ejecución de optimización de Rastrigin 3D utilizando Optimización de Partículas
1.4.6 Conclusiones método de optimización de partículas
En el caso de la optimización maximizando las funciones, llegan muy rápido a una solución óptima (dentro de 10 iteraciones). Por otro lado, la optimización minimizando las funciones tardaba un poco más en llegar al óptimo, pero se acercaba mucho al mínimo global.
Estos resultados pueden deberse a la distribución de las partículas por el espacio de búsqueda, permitiendo una optimización más “abierta” a comparación con el método de descenso de gradiente.
1.5 Método de algoritmos evolutivos
Los algoritmos genéticos (AG) son técnicas de búsqueda heurística basadas en procesos de evolución natural . En un AG típico se define una función FITNESS que evalúa la calidad de cada solución candidata (individuo). A partir de una población inicial aleatoria, se iteran ciclos donde se seleccionan individuos más aptos, se combinan sus “genes” mediante cruces (crossover) y se introducen modificaciones aleatorias (mutaciones). Estos operadores evolucionan la población hacia regiones con mejor fitness.
Según (Scrucca, 2013), los GAs han sido exitosos en optimizar funciones continuas (diferenciables o no) y discretas. Entre los operadores genéticos clave se destacan:
Selección: elige individuos con mayor fitness para reproducirse, imitando la supervivencia del más apto.
Cruce (crossover): combina partes de dos soluciones parentales para generar descendencia, explorando nuevas regiones del espacio de búsqueda.
Mutación: altera aleatoriamente parte de un individuo (por ejemplo, cambiando un valor de su vector de variables) para introducir diversidad genética y evitar estancamiento en óptimos locales.
Los algoritmos genéticos (AG) son metaheurísticas inspiradas en procesos evolutivos biológicos, que han demostrado eficacia en la búsqueda global de óptimos en funciones complejasjstatsoft.org Los AG simulan la selección natural, la recombinación (cruce) y la mutación para iterativamente mejorar un conjunto de soluciones candidatas (población). Estas técnicas estocásticas son adecuadas para funciones no lineales, discontinuas o con múltiples óptimos locales donde los métodos basados en derivadas pueden fallar. Para evaluar la robustez de los GA, se realizarán múltiples ejecuciones independientes y se analizará la dispersión del fitness resultante.
Adicionalmente, se definen algunas funciones para poder mostrar por medio de una animación el proceso de optimización para las funciones de Rosenbrock y de Rastrigin.
Analizaremos cada función en 2 y 3 dimensiones, graficando su paisaje antes de la optimización y luego aplicando un AG con múltiples corridas para evaluar la robustez de los resultados.
1.5.1 Implementación en R de algoritmos evolutivos
Se utiliza la función ga() del paquete GA. Para problemas de minimización se define la función de fitness como el negativo del valor objetivo, ya que ga() maximiza por defecto. Se especifican los límites de búsqueda.
Los resúmenes en cada ejecución reportan el mejor fitness encontrado (negativo) y la solución óptima en cada ejecución.
1.5.2 Optimización de la función de Rastrigin en 2 dimensiones
Animación de la optimización de Rastrigin 2D con Algoritmo Genético
1.5.3 Optimización de la función de Rastrigin en 3 dimensiones
show_table("./Parte 1/Algoritmos_Evolutivos/rastrigin_iter_ae.csv")Iteration <int> |
Mean <dbl> |
Best <dbl> |
|---|---|---|
| 10 | -27.23858 | -9.049369 |
| 20 | -25.13381 | -9.049369 |
| 30 | -18.80389 | -9.009854 |
| 40 | -15.61091 | -9.009854 |
| 50 | -10.47414 | -9.009854 |
| 60 | -16.55153 | -9.009854 |
| 70 | -17.38540 | -9.007921 |
| 80 | -10.28919 | -9.000909 |
| 90 | -16.75012 | -9.000504 |
| 100 | -12.30302 | -9.000344 |
Tabla 7. Tabla de ejecución de optimización de Rastrigin 3D utilizando Algoritmos Evolutivos
1.5.4 Optimización de la función de Rosenbrock en 2 dimensiones
Animación de la optimización de Rosenbrock 2D con Algoritmo Genético
1.5.5 Optimización de la función de Rosenbrock en 3 dimensiones
show_table("./Parte 1/Algoritmos_Evolutivos/rosenbrock_iter_ae.csv")Iteration <int> |
Mean <dbl> |
Best <dbl> |
|---|---|---|
| 10 | -1986.9605 | -31.398720 |
| 20 | -456.4471 | -31.398720 |
| 30 | -1656.6944 | -31.398720 |
| 40 | -781.0234 | -22.941130 |
| 50 | -316.4045 | -15.920770 |
| 60 | -721.8341 | -14.043030 |
| 70 | -941.6848 | -5.756500 |
| 80 | -1501.3154 | -4.130807 |
| 90 | -396.4700 | -1.327077 |
| 100 | -1138.0842 | -1.327077 |
Tabla 8. Tabla de ejecución de optimización de Rosenbrock 3D utilizando Algoritmos Evolutivos
1.5.6 Cálculo de estadísticas y análisis
Para evaluar la variabilidad del método estocástico, se repite cada caso al menos 30 veces con semillas distintas. Se registra el mejor valor de fitness (valorizado positivamente) obtenido en cada corrida. Se calcularán estadísticas (media y desviación estándar) del mejor valor de fitness obtenido en 30 ejecuciones independientes de cada caso y se resumirán en una tabla.
Con los vectores de mejores valores (best_vals_ros, etc.), se calculan la media y desviación estándar de cada conjunto de 30 resultados. Por ejemplo, mean_ros y sd_ros arriba y las demas, Para asi presentar los resultados.
Los resultados de las múltiples ejecuciones se resumen en la Tabla 1. Esta tabla muestra la media y desviación estándar del mejor valor de fitness (recordado que es el valor de la función objetivo en su mínimo global, típicamente cercano a 0) para cada combinación de función y dimensión. Se observa que para Rosenbrock 2D, la media del fitness mínimo es cercana a 0 con baja dispersión, reflejando que el GA normalmente encuentra el mínimo global (0) o cercano. Para Rastrigin 2D, la media también puede acercarse a 0, pero con mayor desviación estándar debido a los múltiples mínimos locales. En 3D ambos problemas suelen mostrar valores medios mayores (más alejados de 0) y mayor variabilidad, lo cual indica una mayor dificultad de búsqueda al aumentar la dimensionalidad.
| Función | Dimensión | Media | SD |
|---|---|---|---|
| Rosenbrock | 2D | 0.0285904 | 0.0460372 |
| Rastrigin | 2D | 0.0001494 | 0.0004027 |
| Rosenbrock | 3D | 3.3777375 | 2.8046450 |
| Rastrigin | 3D | 9.0002470 | 0.0009913 |
Tabla 9. Estadísticas (media y desviación estándar) del fitness mínimo alcanzado en 30 corridas independientes para cada función y dimensión.
1.5.7 Conclusiones método de algoritmos evolutivos
Los resultados confirman que el algoritmo genético es capaz de aproximarse a los mínimos globales de ambos problemas en múltiples dimensiones. Como era de esperar, Rastrigin mostró mayor variabilidad en los valores de fitness debido a sus muchos mínimos locales, lo que implica que algunas ejecuciones del GA pueden quedarse atrapadas en óptimos locales alejados del global. En contraste, Rosenbrock (aunque es no convexa) tiende a un único valle principal; por ello, la mayoría de las corridas alcanzaron valores cercanos al mínimo global con menor dispersión. En general se observa que al aumentar la dimensión (de 2D a 3D) la tarea se complica y la media del fitness aumenta (peor óptimo encontrado), reflejando la maldición de la dimensionalidad. El uso de múltiples ejecuciones independientes es esencial para evaluar la robustez de los AG. Debido a su naturaleza estocástica, cada ejecución puede converger a soluciones distintas. Al analizar la media y desviación estándar de los fitness finales se obtiene una medida de fiabilidad del algoritmo: una baja desviación indica resultados consistentes. En la literatura sobre algoritmos genéticos se reconoce que en muchos casos una sola ejecución puede no ser representativajstatsoft.org. Aunque un análisis comparativo profundo (p.ej., usando poblaciones más grandes o múltiples corridas en paralelo) queda fuera del alcance de este documento, nuestros resultados ilustran este fenómeno. Este estudio es reproducible: todo el código R necesario está incluido, permitiendo a otros investigadores replicar los experimentos, variar parámetros del GA (tasa de cruce, mutación, tamaño de población, etc.) y comparar con otros algoritmos de optimización.:Conclusiones Se ha presentado una documentación completa de la optimización de las funciones de Rosenbrock y Rastrigin en 2D y 3D empleando algoritmos genéticos en R. Mediante visualizaciones 3D iniciales se ilustraron las características de cada función de prueba. Se implementó el paquete GA para resolver cada caso y se realizaron 30 ejecuciones independientes para evaluar la robustez. Los resultados muestran que el GA puede encontrar aproximaciones al mínimo global en ambos problemas, aunque la función Rastrigin (múltiples mínimos locales) presenta más variabilidad y dificultad, especialmente en 3D. # Conclusión General
Al terminar este trabajo, la verdad es que uno se da cuenta de lo poderosos y flexibles que pueden ser los algoritmos bioinspirados cuando se trata de resolver problemas de optimización, tanto numéricos como combinatorios. En la primera parte, experimentamos con funciones clásicas como Rosenbrock y Rastrigin usando métodos como el descenso de gradiente, PSO y algoritmos genéticos. Lo interesante fue ver cómo los métodos bioinspirados, inspirados en la naturaleza y el comportamiento colectivo, logran escapar de los mínimos locales y explorar el espacio de soluciones de una forma mucho más creativa y robusta que los métodos tradicionales. No solo es cuestión de encontrar el mínimo, sino de cómo se llega a él: la diversidad, la colaboración y la adaptación constante hacen la diferencia.
Pero la cosa no se quedó ahí. En la segunda parte, nos metimos de lleno en la optimización combinatoria, enfrentándonos al clásico problema del viajante usando colonia de hormigas. Aquí, la inspiración en el comportamiento de las hormigas para encontrar rutas óptimas en la naturaleza se tradujo en un algoritmo capaz de encontrar soluciones eficientes en problemas donde la cantidad de combinaciones posibles es abrumadora. Es impresionante ver cómo, a través de la cooperación y la comunicación indirecta (como las feromonas en el caso de las hormigas), el sistema encuentra caminos cada vez mejores, incluso cuando el espacio de búsqueda es gigantesco.
En resumen, este trabajo no solo nos permitió comparar y entender diferentes algoritmos, sino que también nos mostró la importancia de pensar “fuera de la caja” y de inspirarnos en la naturaleza para resolver problemas complejos. Los algoritmos bioinspirados no son una receta mágica, pero sí una herramienta poderosa y adaptable, capaz de enfrentar desafíos tanto en el mundo continuo como en el discreto. Además, trabajar con estos métodos fomenta la creatividad, el trabajo en equipo y una visión interdisciplinaria que, sin duda, es clave en la ciencia y la ingeniería de hoy.
Parte 2. Optimización combinatoria
2.1 Planteamiento del problema
Este trabajo resuelve el problema del viajero (TSP) para un vendedor que debe visitar 13 ciudades principales de Colombia, optimizando la ruta mediante Ant Colony Optimization (ACO) y Algoritmos Genéticos (GA). Los costos totales se calculan considerando: - Tiempo del vendedor: Costos por hora de $30,000, $50,000 y $70,000 COP, con una velocidad promedio de 60 km/h. - Peajes: Costos exactos basados en datos de INVIAS y colombiapeajes.com, ajustados al 10% de incremento para abril de 2025. - Combustible: Vehículo DFSK C35 con rendimiento de 10 km/litro y gasolina a $16,000 COP/galón.
La solución óptima se visualiza con un GIF animado que muestra un carrito recorriendo las carreteras principales entre las ciudades.
# Definimos las 13 ciudades principales con sus coordenadas geográficas.
ciudades <- data.frame(
Ciudad = c("Bogotá", "Medellín", "Cali", "Barranquilla", "Cartagena", "Bucaramanga",
"Pereira", "Cúcuta", "Ibagué", "Manizales", "Santa Marta", "Villavicencio", "Pasto"),
Latitud = c(4.6097, 6.2518, 3.4372, 10.9685, 10.3997, 7.1254, 4.8133, 7.8939,
4.4389, 5.0689, 11.2408, 4.1420, 1.2136),
Longitud = c(-74.0817, -75.5638, -76.5225, -74.7813, -75.5144, -73.1198, -75.6961,
-72.5078, -75.2322, -75.5174, -74.1990, -73.6266, -77.2811)
)
#Usamos una matriz de distancias (en km) basada en rutas principales por carretera.
distancias <- matrix(c(
0, 426, 460, 1002, 1068, 384, 306, 552, 174, 257, 1008, 165, 893,
426, 0, 418, 876, 941, 463, 142, 628, 328, 166, 886, 595, 774,
460, 418, 0, 1138, 1203, 595, 259, 760, 296, 341, 1144, 627, 416,
1002, 876, 1138, 0, 122, 618, 1016, 664, 1176, 1019, 122, 837, 1365,
1068, 941, 1203, 122, 0, 683, 1081, 729, 1241, 1084, 187, 902, 1430,
384, 463, 595, 618, 683, 0, 458, 168, 558, 401, 624, 419, 1017,
306, 142, 259, 1016, 1081, 458, 0, 623, 323, 24, 1026, 590, 769,
552, 628, 760, 664, 729, 168, 623, 0, 726, 566, 672, 587, 1185,
174, 328, 296, 1176, 1241, 558, 323, 726, 0, 247, 1182, 339, 729,
257, 166, 341, 1019, 1084, 401, 24, 566, 247, 0, 1029, 432, 712,
1008, 886, 1144, 122, 187, 624, 1026, 672, 1182, 1029, 0, 843, 1371,
165, 595, 627, 837, 902, 419, 590, 587, 339, 432, 843, 0, 858,
893, 774, 416, 1365, 1430, 1017, 769, 1185, 729, 712, 1371, 858, 0
), nrow=13, byrow=TRUE)
rownames(distancias) <- colnames(distancias) <- ciudades$CiudadEl objetivo de este problema es optimizar con respecto a los costos y no a las distancias entre ciudades, por lo que se tienen que considerar los costos de combustible, de peajes y cuánto cobra el vendedor por hora de trabajo. Sin embargo, la distancia afectará al valor de todos estos costos, y por lo tanto hay que considerarla. Adicionalmente, todos estos costos están en función de la distancia en metros, por lo que es necesario realizar la conversión de latitud-longitud a coordenadas en metros. Para esto se usó la librería “sf” para realizar la conversión al sistema de coordenadas planas UTM, el cual representa los puntos del globo en metros.
Luego, se crea la matriz de distancias en metros entre cada ciudad.
Ahora, hay que considerar los costos para poder crear una matriz de costos para resolver el problema de optimización.
Con respecto al costo del combustible, este dependerá del vehículo que el vendedor utilizará para realizar las entregas. Para este problema, se utilizará un furgón DFSK C35, el cual tiene un consumo de combustible de 7.6 litros aproximado por cada 100 Km de recorrido, que se puede traducir en 0.000076 litros por cada 1 metro (DFSK, s.f., Especificaciones Furgon C35). Adicionalmente, se considera el precio promedio de la gasolina en Colombia que, segun (La República, 2025), tiene un valor de $15.827 pesos colombianos por galón, que se puede traducir en $4.022 pesos colombianos por litro aproximadamente.
gasto_litro_por_metro <- 0.000076
precio_gasolina_por_litro <- 4.022
costos_combustible <- distancias * gasto_litro_por_metro * precio_gasolina_por_litro
rownames(costos_combustible) <- nombre_ciudades
colnames(costos_combustible) <- nombre_ciudades
print(costos_combustible)Considerando el costo de los peajes, se usarán los datos de (Invias, 2024) y (Mintransporte, 2025) para calcular el valor promedio de cada peaje de las ciudades consideradas y se asumirá que el vendedor pagará el valor promedio del peaje de la ciudad de origen y de la ciudad de destino exactamente 1 vez cada que las recorra.
#Matriz de costos totales de peajes (en COP), basada en datos reales ajustados al ~10% de incremento para abril de 2025.
costo_peajes <- matrix(c(
0, 60000, 65000, 100000, 110000, 65000, 40000, 70000, 25000, 40000, 100000, 40000, 90000, # Bogotá
60000, 0, 55000, 90000, 100000, 65000, 30000, 80000, 40000, 30000, 90000, 80000, 80000, # Medellín
65000, 55000, 0, 130000, 140000, 90000, 40000, 100000, 40000, 50000, 130000, 80000, 50000, # Cali
100000, 90000, 130000, 0, 21800, 80000, 120000, 90000, 140000, 120000, 21800, 90000, 170000, # Barranquilla
110000, 100000, 140000, 21800, 0, 90000, 130000, 100000, 150000, 130000, 43600, 100000, 180000, # Cartagena
65000, 65000, 90000, 80000, 90000, 0, 80000, 25000, 80000, 65000, 80000, 50000, 130000, # Bucaramanga
40000, 30000, 40000, 120000, 130000, 80000, 0, 90000, 25000, 15000, 120000, 65000, 80000, # Pereira
70000, 80000, 100000, 90000, 100000, 25000, 90000, 0, 90000, 80000, 90000, 65000, 140000, # Cúcuta
25000, 40000, 40000, 140000, 150000, 80000, 25000, 90000, 0, 25000, 140000, 40000, 80000, # Ibagué
40000, 30000, 50000, 120000, 130000, 65000, 15000, 80000, 25000, 0, 120000, 50000, 65000, # Manizales
100000, 90000, 130000, 21800, 43600, 80000, 120000, 90000, 140000, 120000, 0, 90000, 170000, # Santa Marta
40000, 80000, 80000, 90000, 100000, 50000, 65000, 65000, 40000, 50000, 90000, 0, 120000, # Villavicencio
90000, 80000, 50000, 170000, 180000, 130000, 80000, 140000, 80000, 65000, 170000, 120000, 0 # Pasto
), nrow=13, byrow=TRUE)
rownames(costo_peajes) <- colnames(costo_peajes) <- ciudades$CiudadPor último, se debe de considerar el salario por horas promedio de un vendedor que haga dichos recorridos para entregar los pedidos. Adicional a ser vendedor, esta persona realizará las entregas y la conducción de la mercancía, por lo que también hay que considerar su pago como transportista. Dicho esto, se promediaron salarios de un transportista y un vendedor para poder determinar el salario final de la persona. Según (Talent.com, s.f., Salario medio para Transporte De Carga en Colombia 2025) y (Talent.com, s.f., Salario medio para Vendedor en Colombia 2025), un transportista gana en promedio $9.341 pesos colombianos la hora y un vendedor hace $7.144 la hora; por lo tanto, el salario a utilizar será el $8.242 pesos la hora.
Asumiendo que el vendedor conducirá a una velocidad media de 50 km/h al día, que se podrían traducir en 50000 m/h para facilitar cálculos, se procede a calcular el tiempo de viaje y, junto con esto, cuánto se le pagará al vendedor por cada viaje.
velocidad_media_metros_por_hora <- 50000
salario_vendedor_colombia <- 7144
salario_transportista_colombia <- 9341
salario_final <- (salario_vendedor_colombia + salario_transportista_colombia)/2
costos_vendedor <- distancias*(1/velocidad_media_metros_por_hora)*salario_final
rownames(costos_vendedor) <- nombre_ciudades
colnames(costos_vendedor) <- nombre_ciudades
costos_vendedor
Concluyendo, la matriz de costos simplemente sería el resultado de la suma de las anteriores matrices previamente definidas, y esta será la matriz que se utilizarán en los distintos algoritmos para encontrar la mejor ruta.
Se calculan los costos totales considerando - Tiempo : Velocidad promedio de 60 km/h, - Costos por hora $30,000,$50,000,$70,000 COP. - Combustible: DFSK C35 con 10km/litro, gasolina a $16,000 COP/galon.
# Costo de combustible
costo_combustible_km <- 16000 / (10 * 3.785) # ≈ 422.72 COP/km
# Fuente: Precio estimado para 2025, rendimiento DFSK C35 (especificaciones del fabricante)
# Función para calcular costos
calcular_costos <- function(costo_hora) {
tiempos <- distancias / 60 # Tiempo en horas
costo_tiempo <- tiempos * costo_hora
costo_combustible <- distancias * costo_combustible_km
costo_total <- costo_tiempo + costo_combustible + costo_peajes
return(costo_total)
}
# Calcular matrices de costos
costo_hora <- c(30000, 50000, 70000)
matrices_costos <- lapply(costo_hora, calcular_costos)
## 2.2 Implementación Método de Colonia de hormigas Se implementa Ant
Colony Optimizacion(ACO) para optimizar TSP.
Este Algoritmo (ACO) esta inspirado en el comportamiento de
hormigas,este algoritmo simula como las hormigas encuentran la ruta mas
corta dejando feromonas. la idea en si es que la ruta mas corta
acumulara mas feromonas con el tiempo.
aco_tsp <- function(costo_matriz, n_ants=100, alpha=1, beta=2, rho=0.1, max_iter=200) {
n <- nrow(costo_matriz)
pheromones <- matrix(1, nrow=n, ncol=n)
best_tour <- NULL # Almacena la mejor ruta encontrada
best_cost <- Inf # Almacena el costo mínimo inicial (infinito)
history <- list() # Registra el progreso de las iteraciones
for (iter in 1:max_iter) { # Bucle principal para iteraciones (máximo 200)
tours <- matrix(NA, nrow=n_ants, ncol=n) # Matriz para almacenar rutas de todas las hormigas
costs <- numeric(n_ants) # Vector para costos de cada hormiga
for (ant in 1:n_ants) { # Simula el movimiento de cada hormiga (100 por iteración)
current <- sample(1:n, 1) # Comienza en una ciudad aleatoria
tour <- current # Inicializa la ruta con la ciudad actual
visited <- rep(FALSE, n) # Marca ciudades visitadas
visited[current] <- TRUE
for (i in 1:(n-1)) { # Construye la ruta visitando todas las ciudades
probs <- (pheromones[current,] ^ alpha) * ((1 / costo_matriz[current,]) ^ beta)
probs[visited] <- 0
probs <- probs / sum(probs)
next_city <- sample(1:n, 1, prob=probs) # Normaliza probabilidades
tour <- c(tour, next_city)
visited[next_city] <- TRUE
current <- next_city
}
# Asignar tour sin el retorno (longitud n)
tours[ant,] <- tour[1:n] # Tomamos solo las n ciudades
# Calcular costo incluyendo el retorno a la ciudad inicial
tour_with_return <- c(tour, tour[1])
cost <- sum(costo_matriz[cbind(tour_with_return[-n-1], tour_with_return[-1])])
costs[ant] <- cost
if (cost < best_cost) {
best_cost <- cost
best_tour <- tour_with_return
}
}
# Actualizar feromonas
pheromones <- pheromones * (1 - rho)
for (ant in 1:n_ants) {
tour_with_return <- c(tours[ant,], tours[ant,1]) # Cerrar el ciclo para feromonas
pheromones[cbind(tour_with_return[-n-1], tour_with_return[-1])] <-
pheromones[cbind(tour_with_return[-n-1], tour_with_return[-1])] + 1 / costs[ant]
}
history[[iter]] <- list(tour=best_tour, cost=best_cost)
}
return(list(best_tour=best_tour, best_cost=best_cost, history=history))
}2.3 Implementación Método de Algoritmos Genéticos
Se utiliza el paquete de GA para optimizar el TSP. Acá se usa el Algoritmo Genético(GA) esta inspirado en la evolución y selección natural. Este algoritmo evoluciona una población de soluciones(rutas) mediante cruzamiento y mutación la “aptitud” mide que tan buena es una ruta y las mejores rutas se van combinando para mejorar.
# Número de ciudades
n_ciudades <- 13
# Función para normalizar la matriz de costos, ya que search_tour_ants
# funciona con valores normalizados.
# Se optó por usar normalización zscore.
normalize_zscore <- function(m) {
(m - mean(m)) / sd(m)
}
# Normalización de matriz de costos
matriz_costos_normalizada <- normalize_zscore(matriz_costos)
# Ejecución del método de colonia de hormigas
recorrido_optimizado <- search_tour_ants(matriz_costos_normalizada, n_ciudades, K = 80, N = 40, log=TRUE)
print("MEJOR RECORRIDO: ")
print(recorrido_optimizado$tour)A partir de lo anterior se pudo crear el siguiente mapa de rutas que muestra las mejores rutas calculadas por los algoritmos previamente implementados.
